package easy;

public class Solution_LCP_18 {

    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        int drink_min = 100001, drink_max = 0;
        for (int drink : drinks) {
            if (drink > drink_max) {
                drink_max = drink;
            }
            if (drink < drink_min) {
                drink_min = drink;
            }

        }
        int[] drink_counts = new int[drink_max - drink_min + 1];
        for (int drink : drinks) {
            drink_counts[drink - drink_min]++;
        }
        for (int i = 1; i < drink_counts.length; i++) {
            drink_counts[i] += drink_counts[i - 1];
        }

        int staple_min = 100001, staple_max = 0;
        for (int item : staple) {
            if (item > staple_max) {
                staple_max = item;
            }
            if (item < staple_min) {
                staple_min = item;
            }

        }
        int[] staple_counts = new int[staple_max - staple_min + 1];
        for (int item : staple) {
            staple_counts[item - staple_min]++;
        }

        int count = 0;
        for (int i = 0; i < staple_counts.length; i++) {
            if (staple_counts[i] > 0) {
                int sub = x - i - staple_min - drink_min;
                if (sub >= 0) {
                    sub = Math.min(sub, drink_counts.length - 1);
                    count += staple_counts[i] * drink_counts[sub];
                    count %= 1000000007;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution_LCP_18 model = new Solution_LCP_18();
//        System.out.println(model.breakfastNumber(new int[]{10, 20, 5}, new int[]{5, 5, 2}, 15));
        System.out.println(model.breakfastNumber(new int[]{4, 3, 6, 10, 9, 3, 9, 9, 1}, new int[]{2, 5, 7, 5, 6, 2, 5, 8, 6, 10}, 5));
    }
}
